package leetcode_day._2022._202208._2131;

import general_class.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 655. 输出二叉树
 * 算法：广度优先搜索 + 模拟
 *
 * @author yzh
 * @version 1.0
 * @date 2022/8/22 22:11
 */
public class _22 {
    List<List<String>> ans;
    int h, m, n;

    public List<List<String>> printTree(TreeNode root) {
        m = dfs1(root, 0);
        h = m - 1;
        n = (1 << m) - 1;
        ans = new ArrayList<>(m);
        for (int i = 0; i < m; i++) {
            List<String> list = new ArrayList<>(n);
            for (int j = 0; j < n; j++) list.add("");
            ans.add(list);
        }
        dfs2(root, 0, (n - 1) / 2);
        return ans;
    }

    int dfs1(TreeNode node, int depth) {
        if (node == null) return depth;
        return Math.max(dfs1(node.left, depth), dfs1(node.right, depth)) + 1;
    }

    void dfs2(TreeNode node, int x, int y) {
        if (node == null) return;
        ans.get(x).set(y, String.valueOf(node.val));
        dfs2(node.left, x + 1, y - (1 << (h - x - 1)));
        dfs2(node.right, x + 1, y + (1 << (h - x - 1)));
    }

}
